#include<iostream>
namespace MyBST{
  template<class T>
    class TreeNode{
    public:
      typedef TreeNode TNode;
      TreeNode(const T& val):
        _left(nullptr)
        ,_right(nullptr)
        ,_val(val)
      {}
      ~TreeNode()
      {

      }
      TNode* _left;
      TNode* _right;
      T _val;
    };
  template<class T>
    class BSTree{
      public:
        typedef TreeNode<T> TNode;
        BSTree()
          :_root(nullptr)
        {}
        bool push(const T& val)
        {
          if(_root == nullptr)
          {
            _root = new TNode(val);
            return true;
          }
          TNode* parent = nullptr;
          TNode* next = _root;
          while(next)
          {
            if(next->_val > val)
            {
              parent = next;
              next = next->_left;
            }
            else if(next->_val < val)
            {
              parent = next;
              next = next->_right;
            }
            else{
              return false;
            }
          }
            TNode* newnode = new TNode(val);
            if(parent->_val > val)
            {
              parent->_left = newnode;
            }
            else{
              parent->_right = newnode; 
            }
            return true;
          
        }
        void pop_have_nullptr()
        {

        }
        bool pop(const T& val)
        {
          if(_root == nullptr)
          {
            return false;
          }
          TNode* parent = nullptr;
          TNode* child = _root;
          while(child)
          {
            if(child->_val == val)
            {
              //1. child < 2
              if(child->_left == nullptr)
              {
                // only root
                if(child == _root)
                {
                  _root = child->_right;
                  delete child;
                  break;
                }
                if(parent->_left == child)
                {
                  parent->_left = child->_right;
                }
                else if(parent->_right == child)
                {
                  parent->_right = child->_right;
                }
                delete child;
                child = nullptr;
                break;
              }
              else if(child->_right == nullptr)
              {
                //only root
                if(child == _root)
                {
                  _root = child->_left;
                  delete child;
                  break;
                }
                if(parent->_left == child)
                {
                  parent->_left = child->_left;
                }
                else if(parent->_right == child)
                {
                  parent->_right = child->_left;
                }
                delete child;
                child = nullptr;
                break;
              }
              //2.child == 2
              else{
                // find right tree min
                TNode* MinP = child;
                TNode* RightMin = child->_right;
                while(RightMin->_left)
                {
                  MinP = RightMin;
                  RightMin = RightMin->_left;
                }
                std::swap(child->_val,RightMin->_val);
                if(MinP->_right == RightMin)
                {
                  MinP->_right = RightMin->_right;
                }
                else{
                  MinP->_left = RightMin->_right;
                }
                delete RightMin;
                RightMin = nullptr;
                break;
              }
            }
            else if(child->_val > val)
            {
              parent = child;
              child = child->_left;
            }
            else{
              parent = child;
              child = child->_right;
            }

          }
        }
        void print()
        {
          _print(_root);
        }
      private:
        void _print(TNode* root)
        {
          if(root == nullptr)
          {
            return;
          }
          _print(root->_left);
          std::cout << root->_val << " ";
          _print(root->_right);
        }
      public:
        TNode* _root;

    };
}
